Recently, the NTRU cryptosystem has been receiving attention because the NTRU cryptosystem can be implemented in a processor that has a comparatively low processing capability, typically used in home electrical appliances.
In the NTRU cryptosystem, a polynomial operation (addition and multiplication) is the basic operation, and each coefficient of the polynomial is 8 bits or below. Therefore even an 8-bit CPU can easily implement the NTRU cryptosystem. The NTRU cryptosystem is performed at 10-50 times as higher speed than an elliptic curve encryption, and does not necessitate a multiple precision arithmetic library that the elliptic curve encryption would require. The NTRU cryptosystem therefore has an advantage in having smaller code size than the elliptic curve encryption. The NTRU cryptosystem is detailed in non-patent reference 1 and in patent reference 1, and therefore is not described here.
However, sometimes the NTRU cryptosystem has a possibility of causing an error in decryption, and the occurrence of error is not detected at the time of decryption. This is a problem regarding the NTRU cryptosystem, because encryption cannot be guaranteed to be correctly performed.
To solve this problem, the patent reference 2 takes the following approach. Specifically, the transmission apparatus performs a one-way function on a plain text to generate a first functional value, generates first addition information, performs an invertible operation on the plain text and on the first addition information to generate concatenation information, and performs an encryption algorithm on the concatenation information to generate a cipher text. The reception apparatus generates second addition information that is identical to the first addition information, performs a decryption algorithm on the cipher text to generate decryption concatenation information, performs an inverse operation of the invertible operation on the decryption concatenation information and on the second addition information to generate a decrypted text, performs the one-way function on the decrypted text to generate a second functional value, compares the first functional value and the second functional value, and if the values are identical to each other, the decrypted text is judged to be correct. In the above way, it becomes possible to judge whether the plain text has been correctly decrypted.
If a plain text is judged to have been incorrectly decrypted, the receiving party can request that the transmitting party should re-transmit the cipher text, and receive the cipher text again.    (non-patent reference 1)    Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman, “NTRU: A ring based public key cryptosystem”, Lecture Notes in Computer Science, 1423, pp. 267-288, Springer-Verlag, 1998    (patent reference 1)    U.S. Pat. No. 6,081,597    (patent reference 2)    Japanese Laid-open Patent application No. 2002-252611    (non-patent reference 2)    J. Proos, “Imperfect Decryption and an Attack on the NTRU Encryption Scheme”, IACR ePrint Archive, 2003/002, (2003)
The non-patent reference 2 discloses an attacking method used for the NTRU cryptosystem. In this attacking method, in an attempt to obtain a key, an attacker transmits arbitrary data to a receiving party, to check whether the receiving party transmits a re-transmission request. This is a problem because this means that security cannot be guaranteed in the NTRU cryptosystem.